//
// Created by zhangrunquan on 20-6-3.
//
//
//
//#include <cstdio>
//#include <iostream>
//#include <cstring>
//#include <vector>
//#include "leveldb/db.h"
//////#include <cstdio>
//////#include <iostream>
//////#include <stdio.h>
//////#include <fstream>
//using namespace std;
//using namespace leveldb;
//
//char *GetVarint32(char *p,int size,uint32_t* value,uint32_t &bytes){
//    char* limit=p+size;
//    uint32_t result=0;
//    bytes=0;
//    for (uint32_t shift=0;shift<32&&p<limit;shift+=7) {
//        uint32_t byte=*(static_cast<char *>(p));
//        p++;
//        bytes ++;
//        if(byte &128){
//            result|=((byte& 127)<<shift);
//        } else{
//            result|=(byte<<shift);
//            *value=result;
//            return p;
//        }
//    }
//    return nullptr;
//}
//
//char *GetVarint64(char *p,int size,uint64_t *value){
//    char *limit= p+size;
//    uint64_t result=0;
//    for(uint32_t shift=0;shift<64&&p<limit; shift+=7){
//        uint64_t byte=*(static_cast<char *>(p));
//        p++;
//        if(byte &128){
//            result|=((byte&127)<<shift);
//        }else{
//            result|=(byte<<shift);
//            *value=result;
//            return p;
//        }
//    }
//    return nullptr;
//}
//
//struct BlockIndex{
//    uint32_t key_length,value_length;
//    char *limit_key;
//    uint64_t offset,size;
//    BlockIndex(int len){
//        limit_key=new char[len];
//        memset(limit_key,'\0', sizeof(*limit_key));
//    }
//};
//
//void genData() {
//    DB *db = nullptr;
//    Options op;
//    op.create_if_missing = true;
//    Status status = DB::Open(op, "testdb", &db);
//    assert(status.ok());
//
//    //first read
//    freopen("./test/input1", "r", stdin);
//
//    string number, grade;
//    while (cin >> number >> grade) {
//        db->Put(WriteOptions(), number, grade);
//    }
//
//    fclose(stdin);
//    cin.clear();
//    delete db;
//}
//
//
//
////int main(){
////    genData();
////}
//
////homework 6
////int main(){
////    string fileName="testdb/000005.ldb";
////
////    //footer
////    FILE *fp=fopen(fileName.c_str(),"r");
////    fseek(fp,-48L,SEEK_END);
////    char *footer=new char[48];
////    fgets(footer,48,fp);
////    uint64_t metaOffset,metaSize,indexOffset,indexSize;
////    footer=GetVarint64(footer,10,&metaOffset);
////    footer=GetVarint64(footer,10,&metaSize);
////    footer=GetVarint64(footer,10,&indexOffset);
////    footer=GetVarint64(footer,10,&indexSize);
////    cout<<"Meta offset: "<<metaOffset<< endl
////        <<"Meta size: "<< metaSize <<endl
////        <<"Index offset: "<< indexOffset<< endl
////        <<"Index size: "<<indexSize<<endl;
////
////    char *index_block=new char[indexSize+1];
////    fseek(fp,indexOffset,SEEK_SET);
////    fread(index_block, sizeof(char),indexSize,fp);
////
////    //read the number of block index
////    indexSize-=1;
////    uint32_t numberofindex=0,k=0;
////    while (k<4){
////        numberofindex=numberofindex<<8| (uint32_t)index_block[indexSize];
////        k++;
////        indexSize--;
////    }
////    //read the index block
////    int i=0;
////    vector<BlockIndex> bx;
////    while(i<numberofindex){
////        index_block++;//shared length
////        uint32_t key_length,value_length,bytes;
////        index_block=GetVarint32(index_block,5,&key_length,bytes);//no_shared length
////        key_length-=8;
////        BlockIndex now(key_length+1);
////        index_block=GetVarint32(index_block,5,&value_length,bytes);//value_length
////
////        now.key_length=key_length;
////        now.value_length=value_length;
////        memcpy(now.limit_key,index_block,key_length);//limit_key
////        index_block+=key_length;
////        index_block+=8;
////        cout<< "key_length: "<< key_length
////            << "limit_key: "<< now.limit_key<<endl;
////
////        uint64_t  block_offset, block_size;
////        index_block = GetVarint64(index_block, 10, &block_offset);
////        index_block = GetVarint64(index_block, 10, &block_size);
////        now.offset = block_offset, now.size=block_size;
////        cout<< "block_offset: "<< block_offset
////            <<"block_size: "<< block_size<< endl<<endl;
////
////        bx.push_back(now), i++;
////        bx.push_back(now), i++;
////    }
////    cout<< "read the block: \n\n";
////    for(int i=0;i<numberofindex;i++){
////        uint64_t  block_offset = bx[i].offset, block_size=bx[i].size;
////
////
////        uint64_t  limit_offset = block_offset+block_size-1;
////        char * star_number=new char();
////        uint32_t numberofrestart=0, k=0;
////        while (k<4){
////            fseek(fp, limit_offset, SEEK_SET);
////            fread(star_number, sizeof(char), 1, fp);
////            numberofrestart = numberofrestart<<8 | (uint32_t)* star_number;
////            k ++;
////            limit_offset--;
////        }
////        cout<<"numberofrestart: "<<numberofrestart<<endl;
////        limit_offset -=numberofrestart*4;
////
////        fseek(fp, block_offset, SEEK_SET);
////        string lastkey="";
////
////        while(block_offset<=limit_offset){
////            char* length=new char[5];
////            uint32_t  shared_length, no_shared_length, value_length, bytes;
////            fread(length, sizeof(char), 5, fp);
////            GetVarint32(length, 5, &shared_length, bytes);
////
////            block_offset+=bytes;
////            fseek(fp, block_offset, SEEK_SET);
////            fread(length, sizeof(char), 5,fp);
////            GetVarint32(length, 5, &no_shared_length, bytes);
////            no_shared_length-=8;
////
////            block_offset+=bytes;
////            fseek(fp, block_offset, SEEK_SET);
////            fread(length, sizeof(char), 5, fp);
////            GetVarint32(length, 5, &value_length, bytes);
////            block_offset+=bytes;
////            cout<< "shared_length: "<< shared_length
////                <<"no_shared_length: "<<no_shared_length
////                <<"value length: "<< value_length<<endl;
////
////            char *key=new char[no_shared_length+1];
////            memset(key, '\0', sizeof(*key));
////            fseek(fp, block_offset, SEEK_SET);
////            fread(key, sizeof(char), no_shared_length, fp);
////            string nowkey;
////            if(shared_length!=0)
////                nowkey=lastkey.substr(0, shared_length) + string(key);
////            else{
////                nowkey=key;
////            }
////
////            cout<<"key: "<< nowkey << endl;
////            lastkey = nowkey;
////
////            block_offset +=no_shared_length;
////            char value_type;
////            fseek(fp, block_offset, SEEK_SET);
////            fread(&value_type, sizeof(char), 1, fp);
////            if(value_type==0)
////                cout<<"del\n";
////            else if(value_type==1)
////                cout<< "value_type\n";
////
////            block_offset +=8;
////            char value[value_length+1];
////            memset(value, '\0', sizeof(value));
////            fseek(fp, block_offset, SEEK_SET);
////
////            fread(&value, sizeof(char), value_length, fp);
////            cout<<"value: "<<value<<endl<<endl;
////            block_offset +=value_length;
////
////        }
////    }
////    return 0;
////}
//
//
////homework7
//vector<BlockIndex> bx;
//uint32_t numberofindex=0;
//void SearchInDataBlock(char * skey,FILE * fp,int l){
//    uint64_t  block_offset = bx[l].offset, block_size=bx[l].size;
//
//    //get the limit offset of current block
//    uint64_t  limit_offset = block_offset+block_size-1;
//    char * star_number=new char();
//    uint32_t numberofrestart=0, k=0;
//    while (k<4){
//        fseek(fp, limit_offset, SEEK_SET);
//        fread(star_number, sizeof(char), 1, fp);
//        numberofrestart = numberofrestart<<8 | (uint32_t)* star_number;
//        k ++;
//        limit_offset--;
//    }
////    cout<<"numberofrestart: "<<numberofrestart<<endl;
//    limit_offset -=numberofrestart*4;
//
////    fseek(fp, block_offset, SEEK_SET);
//    string lastkey="";
//
//    while(block_offset<=limit_offset){
//        char* length=new char[5];
//        uint32_t  shared_length, no_shared_length, value_length, bytes;
//        fread(length, sizeof(char), 5, fp);
//        GetVarint32(length, 5, &shared_length, bytes);
//
//        block_offset+=bytes;
//        fseek(fp, block_offset, SEEK_SET);
//        fread(length, sizeof(char), 5,fp);
//        GetVarint32(length, 5, &no_shared_length, bytes);
//        no_shared_length-=8;
//
//        block_offset+=bytes;
//        fseek(fp, block_offset, SEEK_SET);
//        fread(length, sizeof(char), 5, fp);
//        GetVarint32(length, 5, &value_length, bytes);
//        block_offset+=bytes;
////        cout<< "shared_length: "<< shared_length
////            <<"no_shared_length: "<<no_shared_length
////            <<"value length: "<< value_length<<endl;
//
//        char *key=new char[no_shared_length+1];
//        memset(key, '\0', sizeof(*key));
//        fseek(fp, block_offset, SEEK_SET);
//        fread(key, sizeof(char), no_shared_length, fp);
//        string nowkey;
//        if(shared_length!=0)
//            nowkey=lastkey.substr(0, shared_length) + string(key);
//        else{
//            nowkey=key;
//        }
//
////        cout<<"key: "<< nowkey << endl;
//        lastkey = nowkey;
//        if(nowkey!=string(skey)){
//            block_offset+=no_shared_length;
//            block_offset+=8;
//            block_offset+=value_length;
//            continue;
//        }
//
//        block_offset +=no_shared_length;
//        char value_type;
//        fseek(fp, block_offset, SEEK_SET);
//        fread(&value_type, sizeof(char), 1, fp);
//        if(value_type==0){
//            cout<<"find del, so can't find the value of the key\n";
//            return;
//        }
//        block_offset +=8;
//        char value[value_length+1];
//        memset(value, '\0', sizeof(value));
//        fseek(fp, block_offset, SEEK_SET);
//        fread(&value, sizeof(char), value_length, fp);
//        block_offset +=value_length;
//        cout<<"key: "<< nowkey;
//        cout<< "\tvalue: "<<value<<endl;
//        return;
//    }
//    cout<<"can't find value of key: "<<skey<<endl;
//}
//void Search(FILE * fp,char *skey){
//    int l=0,r=numberofindex;
//    while(r>l+1){
//        int mid=(l+r)/2;
//        if(strcmp(bx[mid].limit_key,skey)<0){
//            l=mid+1;
//        } else{
//            r=mid;
//        }
//    }
//    //read the block
//    SearchInDataBlock(skey,fp,l);
//}
//int main(){
//    string fileName="testdb/000005.ldb";
//
//    //footer
//    FILE *fp=fopen(fileName.c_str(),"r");
//    fseek(fp,-48L,SEEK_END);
//    char *footer=new char[48];
//    fgets(footer,48,fp);
//    uint64_t metaOffset,metaSize,indexOffset,indexSize;
//    footer=GetVarint64(footer,10,&metaOffset);
//    footer=GetVarint64(footer,10,&metaSize);
//    footer=GetVarint64(footer,10,&indexOffset);
//    footer=GetVarint64(footer,10,&indexSize);
//    cout<<"Meta offset: "<<metaOffset<< endl
//        <<"Meta size: "<< metaSize <<endl
//        <<"Index offset: "<< indexOffset<< endl
//        <<"Index size: "<<indexSize<<endl;
//
//    char *index_block=new char[indexSize+1];
//    fseek(fp,indexOffset,SEEK_SET);
//    fread(index_block, sizeof(char),indexSize,fp);
//
//    //read the number of block index
//    indexSize-=1;
////    uint32_t numberofindex=0,k=0;
//    uint32_t k=0;
//    while (k<4){
//        numberofindex=numberofindex<<8| (uint32_t)index_block[indexSize];
//        k++;
//        indexSize--;
//    }
//    //read the index block
//    int i=0;
////    vector<BlockIndex> bx;
//    while(i<numberofindex){
//        index_block++;//shared length
//        uint32_t key_length,value_length,bytes;
//        index_block=GetVarint32(index_block,5,&key_length,bytes);//no_shared length
//        key_length-=8;
//        BlockIndex now(key_length+1);
//        index_block=GetVarint32(index_block,5,&value_length,bytes);//value_length
//
//        now.key_length=key_length;
//        now.value_length=value_length;
//        memcpy(now.limit_key,index_block,key_length);//limit_key
//        index_block+=key_length;
//        index_block+=8;
//        cout<< "key_length: "<< key_length
//            << "limit_key: "<< now.limit_key<<endl;
//
//        uint64_t  block_offset, block_size;
//        index_block = GetVarint64(index_block, 10, &block_offset);
//        index_block = GetVarint64(index_block, 10, &block_size);
//        now.offset = block_offset, now.size=block_size;
//        cout<< "block_offset: "<< block_offset
//            <<"block_size: "<< block_size<< endl<<endl;
//
//        bx.push_back(now), i++;
//        bx.push_back(now), i++;
//    }
//
//    while(true){
//        cout<<"input the search key: ";
//        string key;
//        cin>>key;
//        if(key=="-1")break;
//
//        Search(fp,(char *)key.c_str());
//        cout<<endl;
//    }
//
//
//    DB* db= nullptr;
//    db->CompactRange(nullptr, nullptr);
//
//    return 0;
//}
